/*
 * Author: 王迪 1300012802
 *
 * Outline:
 * 基于之前我的版本，进行了若干优化。
 *
 * Optimization:
 * 优化0: 大部分数据都进行了离散化，以减小每次做映射的时间。
 * 优化1: 用bitset维护一个人的tag集合，以省去记录每个论坛集合的空间以及
 * 每次查找、判断的时间。
 * 优化2: 用mmap读入数据。
 * 优化3: 对于一个询问，先把对应的导出子图建好，并对点标号进行离散化，以
 * 加快后面的广搜。
 * 优化4: 先读入所有询问，然后在读入论坛信息处理时，如果这个论坛没有询问
 * 中提到的tag，就不用处理了。
 *
 * Performance:
 * 10k的数据在本机跑0.6s。
 */
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>

#include <fast_reader.hpp>

using namespace std;

FastReader reader;

struct Bitset
{
    int width;
    unsigned long long *bits;
    Bitset(int _width)
    {
        width = (_width + 63) >> 6;
        bits = new unsigned long long[width];
        memset(bits, 0, sizeof(unsigned long long) * width);
    }
    ~Bitset()
    {
        delete [] bits;
    }
    inline void set_bit(int k, int x)
    {
        bits[k >> 6] |= 1LL << (k & 63);
        bits[k >> 6] &= ~(((unsigned long long)x ^ 1) << (k & 63));
    }
    inline int get_bit(int k) const
    {
        return (bits[k >> 6] >> (k & 63) & 1);
    }
    void merge(Bitset *bs)
    {
        for (int i = 0; i < width; ++ i)
            bits[i] |= bs->bits[i];
    }
};

unordered_map<int, int> person_id_to_axis;
vector<int> person_axis_to_id;

unordered_set<string> considered_tags;
unordered_map<string, int> tag_name_to_axis;
unordered_map<int, int> tag_id_to_axis;
int tag_cnt;

unordered_map<int, Bitset*> forum_id_to_tags;

vector<Bitset*> person_axis_to_tags;

vector<vector<int>> person_axis_to_persons;

void handlePerson(int person_cnt, const string &data_path)
{
    string person_data_file = data_path + "person.csv";
    reader.fastOpen(person_data_file.c_str());
    int axis_index = 0;
    
    person_id_to_axis.clear();
    person_axis_to_id.resize(person_cnt);
    reader.skipLine();
    while (reader.hasNext())
    {
        int person_id = reader.getInt();
        reader.skipLine();

        person_id_to_axis[person_id] = axis_index;
        person_axis_to_id[axis_index] = person_id;

        ++ axis_index;
    }

    reader.fastClose();
}

void handleTag(const string &data_path)
{
    string tag_data_file = data_path + "tag.csv";
    reader.fastOpen(tag_data_file.c_str());
    int axis_index = 0;

    tag_id_to_axis.clear();
    tag_name_to_axis.clear();
    reader.skipLine();
    while (reader.hasNext())
    {
       int tag_id = reader.getInt();
       string tag_name = reader.getString();
       reader.skipLine();

       if (!considered_tags.count(tag_name)) continue;

       tag_id_to_axis[tag_id] = axis_index;
       tag_name_to_axis[tag_name] = axis_index;

       ++ axis_index;
    }

    tag_cnt = axis_index;
    reader.fastClose();

    person_axis_to_tags.resize(person_axis_to_id.size());
    int person_cnt = person_axis_to_id.size();
    for (int p = 0; p < person_cnt; ++ p)
        person_axis_to_tags[p] = new Bitset(tag_cnt);
}

void handleForumHasTag(const string &data_path)
{
    string forum_has_tag_data_file = data_path + "forum_hasTag_tag.csv";
    reader.fastOpen(forum_has_tag_data_file.c_str());

    forum_id_to_tags.clear();
    reader.skipLine();
    while (reader.hasNext())
    {
        int forum_id = reader.getInt();
        int tag_id = reader.getInt();
        reader.skipLine();

        if (!tag_id_to_axis.count(tag_id)) continue;

        Bitset *tags = NULL;
        if (forum_id_to_tags.count(forum_id) != 0)
            tags = forum_id_to_tags[forum_id];
        else 
        {
            tags = new Bitset(tag_cnt);
            forum_id_to_tags[forum_id] = tags;
        }

        int tag_axis = tag_id_to_axis[tag_id];
        tags->set_bit(tag_axis, 1);
    }

    reader.fastClose();
}

void handleForumHasMember(int person_cnt, const string &data_path)
{
    string forum_has_member_data_file = data_path + "forum_hasMember_person.csv";
    reader.fastOpen(forum_has_member_data_file.c_str());

    person_axis_to_tags.resize(person_cnt, NULL);
    reader.skipLine();
    while (reader.hasNext())
    {
        int forum_id = reader.getInt();
        int person_id = reader.getInt();
        reader.skipLine();

        if (!forum_id_to_tags.count(forum_id)) continue;

        int person_axis = person_id_to_axis[person_id];
        Bitset *tags = person_axis_to_tags[person_axis];

        tags->merge(forum_id_to_tags[forum_id]);
    }

    reader.fastClose();
}

void handlePersonKnowsPerson(int person_cnt, const string &data_path)
{
    string person_knows_person_data_file = data_path + "person_knows_person.csv";
    reader.fastOpen(person_knows_person_data_file.c_str());

    person_axis_to_persons.clear();
    person_axis_to_persons.resize(person_cnt);
    reader.skipLine();
    while (reader.hasNext())
    {
        int person_from_id = reader.getInt();
        int person_to_id = reader.getInt();
        reader.skipLine();

        int person_from_axis = person_id_to_axis[person_from_id];
        int person_to_axis = person_id_to_axis[person_to_id];

        person_axis_to_persons[person_from_axis].push_back(person_to_axis);
    }

    reader.fastClose();
}


vector<int> valid_persons;
vector<vector<int>> valid_person_to_persons;
vector<int> valid_person_axis_to_small_axis;
vector<int> valid_person_small_axis_to_axis;
int *q, *dist, *dfn;
int timestamp;

struct DisjointSet 
{
    vector<int> root;
    vector<int> size;
    void init(int person_cnt)
    {
        root.resize(person_cnt);
        size.resize(person_cnt);
        for (int p = 0; p < person_cnt; ++ p)
        {
            root[p] = p;
            size[p] = 1;
        }
    }
    int get(int x)
    {
        return (x == root[x] ? x : root[x] = get(root[x]));
    }
    void merge(int x, int y)
    {
        x = get(x);
        y = get(y);
        if (x != y)
        {
            if (size[x] > size[y])
                swap(x, y);
            root[x] = y;
            size[y] += size[x];
        }
    }
} ds;

void generateValidPersons(int person_cnt, int tag_axis)
{
    valid_persons.clear();
    valid_person_to_persons.clear();
    valid_person_axis_to_small_axis.resize(person_cnt);
    valid_person_small_axis_to_axis.clear();
    int axis_index = 0;

    for (int p = 0; p < person_cnt; ++ p)
        if (person_axis_to_tags[p]->get_bit(tag_axis))
        {
            valid_persons.push_back(p);
            valid_person_axis_to_small_axis[p] = axis_index;
            valid_person_small_axis_to_axis.push_back(p);
            ++ axis_index;
        }

    ds.init(axis_index);

    valid_person_to_persons.resize(axis_index);
    for (int t = 0; t < axis_index; ++ t)
    {
        int p = valid_person_small_axis_to_axis[t];
        vector<int> &to_persons = person_axis_to_persons[p];
        vector<int> &tmp = valid_person_to_persons[t];
        for (int v : to_persons)
            if (person_axis_to_tags[v]->get_bit(tag_axis)) 
            {
                int s = valid_person_axis_to_small_axis[v];
                tmp.push_back(s);
                ds.merge(t, s);
            }
    }
}

pair<bool, double> calculateClosenessCentrality(int p, double bound)
{
    int block_size = ds.size[ds.get(p)];
    if (block_size == 1)
    {
        return make_pair(false, 0.0);
    }

    int dist_sum = 0;
    int qh = 0, qt = 0;
    ++ timestamp;

    q[qt ++] = p;
    dist[p] = 0;
    dfn[p] = timestamp;
    while (qh != qt)
    {
        int u = q[qh ++];
        vector<int> &to_persons = valid_person_to_persons[u];
        for (int v : to_persons)
        {
            if (dfn[v] < timestamp)
            {
                dist[v] = dist[u] + 1;
                dfn[v] = timestamp;
                dist_sum += dist[v];
                q[qt ++] = v;
            }
        }
        if ((double)(block_size - 1) * (block_size - 1) / (dist_sum + (block_size - qt) * (dist[u] + 1)) < bound) 
            return make_pair(false, 0.0);
    }

    return make_pair(true, (double)(block_size - 1) * (block_size - 1) / dist_sum);
}

int main(int argc, char *argv[])
{
#ifndef LOCAL
    string data_path(argv[1]);
    int person_cnt = atoi(argv[2]);
    string query_file(argv[3]);
    string answer_file(argv[4]);
#else
    string data_path("../../../data/10k-network/");
    int person_cnt = 10000;
    string query_file("../query4.in");
    string answer_file("../query4.out");
#endif

    FILE *f_query = fopen(query_file.c_str(), "r");
    FILE *f_answer = fopen(answer_file.c_str(), "w");

    int k;
    char buf[BUFSIZ];

    while (fscanf(f_query, "%d%s", &k, buf) != EOF)
    {
        considered_tags.insert(string(buf));
    }
    fseek(f_query, 0, SEEK_SET);

    handlePerson(person_cnt, data_path);
    handleTag(data_path);
    handleForumHasTag(data_path);
    handleForumHasMember(person_cnt, data_path);
    handlePersonKnowsPerson(person_cnt, data_path);
    
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> heap;

    q = new int[person_cnt];
    dist = new int[person_cnt];
    dfn = new int[person_cnt];
    timestamp = 0;
    memset(dfn, 0, sizeof(int) * person_cnt);

    while (fscanf(f_query, "%d%s", &k, buf) != EOF)
    {
        int tag_axis = tag_name_to_axis[string(buf)]; 
        generateValidPersons(person_cnt, tag_axis);

        int valid_person_cnt = valid_persons.size();
        for (int p = 0; p < valid_person_cnt; ++ p)
        {
            double bound = 0.0;
            if ((int)heap.size() == k)
                bound = heap.top().first;

            pair<bool, double> closeness_centrality = calculateClosenessCentrality(p, bound);

            if (closeness_centrality.first)
            {
                heap.push(make_pair(closeness_centrality.second, -person_axis_to_id[valid_person_small_axis_to_axis[p]]));

                if ((int)heap.size() > k)
                    heap.pop();
            }
        }

        vector<pair<double, int>> ans;
        while (heap.size())
        {
            ans.push_back(heap.top());
            heap.pop();
        }
        reverse(begin(ans), end(ans));

        for (const auto &v : ans)
            fprintf(f_answer, "%d ", -v.second);
        fprintf(f_answer, "\n");
    }

    fclose(f_query);
    fclose(f_answer);

    delete [] q;
    delete [] dist;
    delete [] dfn;

    for (const auto &v : forum_id_to_tags)
        delete v.second;
    for (auto p : person_axis_to_tags)
        delete p;

    return 0;
}
